/// @tags: SA Diff
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
using std::min;
using std::swap;

namespace BlueQuantum {

typedef long long ll;

int const N = 1e6 + 5, bit = 20;

int T;
int stt[N], end[N];

struct SuffixArray {
  static int n, m;
  static int lg[N];
  int rk[N], sa[N], tmp[N], cnt[N], ht[N];
  int f[N][bit];
  char str[N];

  inline void sort() {
    memset(cnt, 0, sizeof(int) * (m + 1));
    for (int i = 1; i <= n; ++i) cnt[rk[i]]++;
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
  }

  inline void build() {
    m = 27;
    /// @warning 不清空会WA？？？
    memset(tmp, 0, sizeof(tmp));
    for (int i = 1; i <= n; ++i) rk[i] = str[i] - 'a' + 1, tmp[i] = i;
    sort();
    for (int l = 1, p = 0; l <= n; l <<= 1, m = p, p = 0) {
      for (int i = n - l + 1; i <= n; ++i) tmp[++p] = i;
      for (int i = 1; i <= n; ++i)
        if (sa[i] > l) tmp[++p] = sa[i] - l;
      sort();
      memcpy(tmp, rk, sizeof(int) * (p + 1));
      rk[sa[1]] = p = 1;
      for (int i = 2; i <= n; ++i)
        rk[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + l] == tmp[sa[i - 1] + l])
                        ? p
                        : ++p;
    }
    for (int i = 1, j = 0; i <= n; ++i) {
      if (j) --j;
      while (str[i + j] == str[sa[rk[i] - 1] + j]) ++j;
      ht[rk[i]] = j;
    }

    for (int i = 1; i <= n; ++i) f[i][0] = ht[i];
    for (int j = 1; (1 << j) <= n; ++j)
      for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  }

  inline int getLCP(int l, int r) {
    l = rk[l], r = rk[r];
    if (l > r) swap(l, r);
    int k = lg[r - ++l + 1];
    return min(f[l][k], f[r - (1 << k) + 1][k]);
  }

} nor, rev;

int SuffixArray::n, SuffixArray::m;
int SuffixArray::lg[N];

inline int main() {
  SuffixArray::lg[0] = -1;
  for (int i = 1; i < N; ++i) SuffixArray::lg[i] = SuffixArray::lg[i >> 1] + 1;
  SuffixArray::lg[0] = 0;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", nor.str + 1);
    int n = strlen(nor.str + 1);
    SuffixArray::n = n;
    memset(stt, 0, sizeof(stt));
    memset(end, 0, sizeof(end));
    for (int i = 1; i <= n; ++i) rev.str[i] = nor.str[n - i + 1];
    nor.build(), rev.build();
    for (int len = 1; len <= n >> 1; ++len) {
      for (int i = len; i + len <= n; i += len) {
        int norL = i, norR = i + len;
        int revL = n - (norR - 1) + 1, revR = n - (norL - 1) + 1;
        int lcp = min(nor.getLCP(norL, norR), len);
        int lcs = min(rev.getLCP(revL, revR), len - 1);
        if (lcp + lcs >= len) {
          end[i - lcs]++, end[i - lcs + (lcp + lcs - len + 1)]--;
          stt[norR + lcp - (lcp + lcs - len + 1)]++, stt[norR + lcp]--;
        }
      }
    }
    for (int i = 1; i <= n; ++i) stt[i] += stt[i - 1], end[i] += end[i - 1];
    ll ans = 0;
    for (int i = 1; i < n; ++i) ans += 1ll * stt[i] * end[i + 1];
    printf("%lld\n", ans);
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P1117 [NOI2016] 优秀的拆分.in", "r", stdin);
  freopen("P1117 [NOI2016] 优秀的拆分.out", "w", stdout);
#endif
#endif

  return BlueQuantum::main();
}